package com.example;


/**
 * @Author loubobooo
 * @Description #24两两交换链表中的节点
 * @Date 2022/4/14
 */
public class SwapNodesInPairs {

    /**
     * @Author loubobooo
     * @Description 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     * @Date 2022/4/14
     * @Param
     * @return
     **/
    public ListNode swapPairs(ListNode head) {
        // 遵循左边指针，指向，右边节点
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur.next != null && cur.next.next != null){
            ListNode node1 = cur.next;
            ListNode node2 = cur.next.next;
            // -1->1->2->3
            // 先断开1->2接上3
            node1.next = node2.next;
            // -1->1->3 和2->3
            // 断开-1->1，接上2
            cur.next = node2;
            // -1->2->3
            // 断开2->3接上1->3
            node2.next = node1;
            // 将当前遍历的节点指向cur.next.next;
            cur = node1;
        }
        return dummyHead.next;
    }

    public ListNode swapPairs2(ListNode head) {
        // 先设置终止条件
        if(head == null || head.next == null){
            return head;
        }
        // 类似于交换两个整数 c = a; a = b; b = c
        ListNode listNode = head.next;
        head.next = swapPairs2(listNode.next);
        listNode.next = head;
        return listNode;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static void main(String[] args) {
        int[] arr2 = {1, 2, 3, 4, 5};
        ListNode node2 = new ListNode(1);
        ListNode temp2 = node2;
        for (int i = 0; i < arr2.length; i++) {
            temp2.next = new ListNode(arr2[i]);
            temp2 = temp2.next;
        }
        SwapNodesInPairs swapNodesInPairs = new SwapNodesInPairs();
        swapNodesInPairs.swapPairs(node2.next);
    }
}
